/*
   @Copyright:LintCode
   @Author:   tjyemail
   @Problem:  http://www.lintcode.com/problem/stone-game
   @Language: C++
   @Datetime: 19-04-12 16:49
   */

class Solution {
public:
	/**
	 * @param A: An integer array
	 * @return: An integer
	 * Tip:
	 * dp[i][j] as min cost in range [i,j],
	 * select k (i<k<j) split range to [i,k], [k+1,j]
	 * notice: dp[i][j] include sum[i][j]
	 */
	int stoneGame(vector<int> &A) {
		// write your code here
		if(A.size()<1) return 0;
		int n=A.size();
		vector<vector<int> > dp(n,vector<int>(n,0));
		vector<int> sums(n,A[0]);
		for(int i=1; i<n; ++i)
			sums[i]=sums[i-1]+A[i];
		for(int len=1; len<=n; ++len){
			for(int i=0; i+len<n; ++i){
				int sum=sums[i+len]-sums[i-1];
				dp[i][i+len]=INT_MAX;
				for(int k=i; k<i+len; ++k){
					dp[i][i+len]=min(dp[i][i+len],dp[i][k]+dp[k+1][i+len]+sum);
				}
			}
		}
		return dp[0][n-1];
	}
};
